/*
 * Copyright (C) 2006 Moritz Tuerk <brotkasten@users.sourceforge.net>
 * 
 * This program is free software; you can redistribute it and/or modify it under the terms 
 * of the GNU General Public License as published by the Free Software Foundation; either 
 * version 2 of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, 
 * but WITHOUT ANY WARRANTY; without even the implied 
 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
 * See the GNU General Public License for more details.
 *  
 *  You should have received a copy of the GNU General Public License along with 
 *  this program; if not, write to the Free Software Foundation, 
 *  Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110, USA
 */
package mo.common.util;

/**
 * This is a minimum implementation of a min heap. It can be used as a priority
 * queue or for sorting comparable elements.<br>
 * 
 * @author brotkasten
 */
public class Heap<T extends Comparable<T>> {
    /**
     * saves the default capacity of the Heap, if no other capacity is set (this
     * means Elements in the heap)
     */
    private final static int DEFAULT_CAPACITY = 10;

    /**
     * defines the capacity growth factor in case of a resize event of the
     * queue, if no other factor was set
     */
    private final static double DEFAULT_GROW_FACTOR = 1.3;

    /**
     * Call this method to get the height of an almost complete binary tree.
     * 
     * @param n
     *            saves the number of nodes in the tree
     * @return the height of the tree
     */
    @SuppressWarnings("unused")
    private static int getTreeHeight(final int n) {
        if (n <= 0) {
            return 0;
        }

        int result = 0;
        int i = n;

        while (i > 0) {
            i >>= 1;
            result++;
        }

        return result;
    }

    /**
     * Debug, only...
     * 
     * @param args
     *            no args !
     */
    public static void main(final String[] args) {
        // simple sort demo (n log n)
        final Integer a[] = new Integer[20];

        for (int i = 0; i < a.length; i++) {
            a[i] = new Integer((int) Math.round(Math.random() * 50.0));
        }
        final Heap<Integer> h = new Heap<Integer>();
        for (final Integer next : a) {
            h.addElement(next);
        }

        for (@SuppressWarnings("unused") final Integer element : a) {
            System.out.println(h.deleteFirst());
        }
    }

    /**
     * saves the current growth factor set for this heap. The factor defines the
     * growth of the heap in case it is resized
     */
    private final double currentGrowth;

    /**
     * saves the Index of the next Element to insert into the heap.
     */
    private int currentIndex;

    /**
     * saves the list of elements in this heap
     */
    private transient T[] elements;

    /**
     * This constructs a new Heap with the default capacity and the default
     * growth factor.
     */
    @SuppressWarnings("unchecked")
    public Heap() {
        this.currentGrowth = Heap.DEFAULT_GROW_FACTOR;
        this.currentIndex = 0;

        this.elements = (T[]) new Comparable[Heap.DEFAULT_CAPACITY];
    }

    /**
     * This can be called to add a new Element to the heap
     * 
     * @param newElement
     *            saves the element to add to the heap
     */
    public void addElement(final T newElement) {
        this.checkAndResize();
        this.elements[this.currentIndex++] = newElement;
        this.restoreHeap(this.elements, this.currentIndex);
    }

    /**
     * This method is called to check the current size of the heap and resizes
     * it as necessary. A check (current size + 1 >= capacity) is done
     */
    @SuppressWarnings("unchecked")
    private void checkAndResize() {
        if (this.currentIndex + 1 >= this.elements.length) {
            // XXX: This one is possibly dangerous ... but as long as the queue
            // XXX: doesn't exceed 2^31 elements it's ok :)
            T newElements[] = (T[]) new Comparable[(int) Math
                    .round(this.elements.length * this.currentGrowth)];

            System.arraycopy(this.elements, 0, newElements, 0,
                    this.elements.length);
            this.elements = newElements;
            newElements = null;
        }
    }

    /**
     * This method can be called to delete the first element from the heap. This
     * is the minimum element. This can be used to use the heap as a priority
     * queue. The element with the highest prio (minimum element) is selected
     * first.
     * 
     * @return the minimum element from the queue.
     */
    public T deleteFirst() {
        if (this.currentIndex == 0) {
            return null;
        }
        final T result = this.elements[0];

        this.elements[0] = this.elements[--this.currentIndex];
        this.elements[this.currentIndex] = null;

        this.restoreHeapReverse(this.elements, 1, this.currentIndex);

        return result;
    }

    /**
     * Call this method to get all the Elements of the heap. The array returned
     * is a vector representation of an almost complete binary tree. <b>DO
     * NOT</b> modify this array, otherwise the heap won't work properly
     * anymore. This is for read only operations. Note that the array is not
     * neccessarily completly filled with elements. Please call {@link #size()}
     * to get the number of elements in the heap.
     * 
     * @return the vector representation of the heap
     */
    public T[] getElements() {
        return this.elements;
    }

    /**
     * This method can be called to get the first element from the heap. This is
     * the minimum element. This can be used for priority queueing.
     * 
     * @return
     */
    public T getFirst() {
        if (this.currentIndex == 0) {
            return null;
        }
        return this.elements[0];
    }

    /**
     * This method is called to restore the heap after inserting an element. It
     * restores the heap from the bottom<br>
     * 
     * <pre>
     *                   1              1
     *               4      8   -&gt;   4     3
     *             6   7 10   3    6   7 10  8
     * </pre>
     */
    private void restoreHeap(final T c[], final int n) {
        if (n < 2) {
            return;
        }

        final int index = n / 2;
        final int left = 2 * index;
        final int right = 2 * index + 1;

        // minimum element of the three elements to compare
        // (root) (left) (right)
        int min = index;

        if (left <= n) {
            if (c[min - 1].compareTo(c[left - 1]) > 0) {
                min = left;
            }
        }
        if (right <= n) {
            if (c[min - 1].compareTo(c[right - 1]) > 0) {
                min = right;
            }
        }

        if (min != index) {
            final T tmp = c[index - 1];
            c[index - 1] = c[min - 1];
            c[min - 1] = tmp;
            this.restoreHeap(c, index);
        }
    }

    /**
     * This method is called to restore the heap after deleting the first
     * element. It restores the heap from the top<br>
     * 
     * <pre>
     *              8              3
     *           4     3   -&gt;   4     8
     *         6   7 10      6   7 10
     * </pre>
     */
    private void restoreHeapReverse(final T c[], final int index, final int n) {
        final int left = 2 * index;
        final int right = 2 * index + 1;

        // minimum element of the three elements to compare
        // (root) (left) (right)
        int min = index;

        if (left <= n) {
            if (c[min - 1].compareTo(c[left - 1]) > 0) {
                min = left;
            }
        }
        if (right <= n) {
            if (c[min - 1].compareTo(c[right - 1]) > 0) {
                min = right;
            }
        }

        if (min != index) {
            final T tmp = c[index - 1];
            c[index - 1] = c[min - 1];
            c[min - 1] = tmp;
            this.restoreHeapReverse(c, min, n);
        }
    }

    /**
     * This method can be called to get the current number of Elements in the
     * Heap (not the capacity)
     * 
     * @return the number of elements stored in the heap
     */
    public int size() {
        return this.currentIndex;
    }
}
